"""
Main file 
"""

g_settings = 0

#Enumerated variables for the roles of the agents
_Loitering = 0
_LookingForAmmo = 1
_GrabbingAmmo = 2
_AttackMove = 3
_Camping = 4
_Combat = 5
_Shooting = 6
_CapturingCP = 7

################################################################################
# Module: UTIL
################################################################################
#def inRangeManhattan(x1, y1, x2, y2, maxRange):
#    return abs(x1 - x2) < maxRange and abs(y1 - y2) < maxRange
def inRangeManhattan(p1, p2, maxRange):
    return abs(p1[0] - p2[0]) < maxRange and abs(p1[1] - p2[1]) < maxRange

def pathLength(loc, path):
    """Calculates the length of a path,
    turning taken into account
    loc: the location of the agent
    path: a list of points in the path, as returned from find_path
    NOTE: maybe we can get this info from the pathfinding algo itsel?
       Would need to edit Thomas' code and get it accepted for the tournament"""
    l = ((loc[0] - path[0][0])**2 + (loc[1] - path[0][1])**2)**0.5
    for i in range(1,len(path)):
        l += ((path[i-1][0] - path[i][0])**2 + (path[i-1][1] - path[i][1])**2)**0.5
    return l

def stepsToTarget(loc, ang, path, length):
    """Calculates the number of steps required to reach a target,
    TODO: taking into account the angles in the path.
    It uses the distance per step, and the number of times
    a step is wasted on turning because the angle is too large.
    Whether this is exact depends on the agent behaviour:
    does it stop to turn or not?
    loc: current location of agent
    ang: current angle of agent
    path: list of points in the path
    length: length of the path, as calculated by pathLength()
    """
    steps = math.ceil(length / g_settings.max_speed)
    steps += math.ceil(getTurns(path, loc,  ang))
    return steps
def getTurns(path,loc,ang):
    turnsteps = 0
    #for first path point
    Turn = abs(getTurn(loc, path[0], ang))
    turnsteps += math.ceil(Turn / g_settings.max_turn)
    
    #for second path point
    if len(path) > 2:
	Turn = abs(getTurn(path[1], path[2], getRotation(path[0], path[1])))
	turnsteps += math.ceil(Turn / g_settings.max_turn)
	if len(path) > 3:
	    for i in range (2,len(path)-1):
		Turn = abs(getTurn(path[i-1], path[i], getRotation(path[i-2], path[i-1])))
		turnsteps += math.ceil(Turn / g_settings.max_turn)
		pass
    return turnsteps
def getRotation(loc, targetloc):
    dx = targetloc[0]-loc[0]
    dy = targetloc[1]-loc[1]
    return math.atan2(dy,dx)
def getTurn(loc, target, ang):
    """
    Gets the rotation required to turn towards a target,
    when standing at loc, with given angle.
    Note: does not truncate turn to the max allowed value,
    so that user code can check if full rotation is possible,
    and choose what to do.
    """
    dx = target[0]-loc[0]
    dy = target[1]-loc[1]
    turn = angle_fix(math.atan2(dy, dx)-ang)
    return turn

def permutations(iterable, r=None): # From itertools.permutations(), but not available in 2.5
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

################################################################################
# Module: INTEL
################################################################################
class Edge(object):
    
    def __init__(self, v1, v2):
        self.v1 = v1
        self.v2 = v2
        self.visitedV1 = False
        self.visitedV2 = False
        self.visited = False # True when any of the vertices have been visited

    def visit(self, point):
        """Tell the edge that you've visited one of the vertices.
        point gives the (x,y) coords of the VERTEX you're visiting (must be exact)"""
        if point == self.v1:
            self.visitedV1 = True
            self.visited = True
            return
        if point == self.v2:
            self.visitedV2 = True
            self.visited = True

    def visitedVertex(self, vertex):
        """Return true if the given vertex was visited"""
        if self.visited:
            if self.v1 == vertex and self.visitedV1:
                return True
            elif self.v2 == vertex and self.visitedV2:
                return True
        return False

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            if self.v1 == other.v1 and self.v2 == other.v2:
                return True
            if self.v2 == other.v1 and self.v1 == other.v2:
                return True
        return False

    def __repr__(self):
        return "Edge: {" + str(self.v1) + ", " + str(self.v2) + "}"
        
        
class Graph(object):
    
    def __init__(self, nav_mesh):
        
        self.edgeDict = {} # maps vertices to edge-lists
        self.edgeList = [] # lists all edges
        self.vertList= []  # lists all vertices
        for v1 in nav_mesh.keys():
            if not v1 in self.vertList:
                self.vertList.append(v1)
                
                for v2 in nav_mesh[v1]:
                    e = Edge(v1,v2)
                    if not e in self.edgeList:
                        self.edgeList.append(e)
                        if v1 in self.edgeDict:
                            self.edgeDict[v1].append(e)
                        else:
                            self.edgeDict[v1] = [e]
                        if v2 in self.edgeDict:
                            self.edgeDict[v2].append(e)
                        else:
                            self.edgeDict[v2] = [e]

    def visit(self, point):
        """Marks all vertices within range of point as visited"""
        for v in self.vertList:
            if inRangeManhattan(v, point, g_settings.max_see):
                for e in self.edgeDict[v]:
                    e.visit(v)
    
    def visited(self, vertex):
        """return true if the vertex was visited"""
        return self.edgeDict[vertex][0].visitedVertex(vertex)

    def unvisited(self, maxVerts = -1):
        """Returns a list of unvisted vertices.
        If maxVerts is given, limits results to maxVerts vertices.
        Otherwise all unvisited vertices are returned."""
        unvisited = []
        if maxVerts == -1:
            maxVerts = len(self.vertList)
        else:
            maxVerts = min(maxVerts, len(self.vertList))

        for i in range(maxVerts):
            if not self.visited(self.vertList[i]):
                unvisited.append(self.vertList[i])

        return unvisited

    def __repr__(self):
        return "Graph: {" + str(self.edgeDict) + "}"

class AmmoPack(object):
    """ This class represents a single ammo pack"""
    def __init__(self, x, y, availableIn = 0, inSight = True):
        self.x = x
        self.y = y
        self.availableIn = availableIn # Time until it becomes available. <= 0 means its available
        self.ammoRate = g_settings.ammo_rate # Time between respawns
        self.inSight = inSight  # Whether this pack was observed or observed to be absent in the current time step
        if inSight:
            self.lastInSight = 0   # How many steps ago this pack was last seen (or seen to be absent)
        else:
            self.lastInSight = 1000 # Pretend it was seen once, long ago (symmetric packs are created without really having been spotted)
        self.requests = [None for i in range(6)] # List of agents that want this pack, with request info

    def frameBegin(self):
        self.inSight = False
        #self.availableIn -= 1
        self.lastInSight += 1
        self.requests = [None for i in range(6)]

    def frameEnd(self):
        self.availableIn -= 1
        # If the pack wasn't inSight, and it should be available by now (availableIn < 0), enemy could pick it up..

    def pickedUp(self): # Call when picked up (either by us or opponent)
        self.availableIn = self.ammoRate
    
    def observedPresent(self): # Call when observed to be present
        if self.availableIn > 0:
            self.availableIn = 0
        self.inSight = True
        self.lastInSight = 0 # Last seen now

    def observedAbsent(self): # Call when you can see the position but pack is not there
        #print "Observed to be absent: " + self.__repr__()
        if self.availableIn <= 0: # It should have been present, but someone picked it up..
            self.pickedUp() #self.availableIn = self.ammoRate # Assume it was picked up just now; probably not realistic
        self.inSight = True    
        self.lastInSight = 0 # Last seen now
    
    def requestAmmo(self, agent):
        path = find_path(agent.observation.loc, (self.x, self.y), agent.mesh, agent.grid, g_settings.tilesize)
        length = pathLength(agent.observation.loc, path)
        steps = stepsToTarget(agent.observation.loc, agent.observation.angle, path, length)
        #agent.aprint("respawn: " + str(agent.observation.respawn_in), agent.id) 
        if agent.observation.respawn_in > 0:  # If the agent is still respawning, take into account the waiting time
            steps += agent.observation.respawn_in
        self.requests[agent.id] = [agent, path, length, steps, False]

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.x == other.x and self.y == other.y
        else:
            return False

    def __repr__(self):
        return "AmmoPack: {x: " + str(self.x) + ", y: " + str(self.y) + \
            ", availableIn: " + str(self.availableIn) + ", inSight: " + \
            str(self.inSight) + ", lastInSight: " + str(self.lastInSight) + "}"

################################################################################
# Module: LEARNING
################################################################################


################################################################################
# Module: AGENTS
################################################################################



class AgentBase:
    NAME = "Tijmens_Remorse"
    ammoPacks = []
    ammoRequestIndices = [] # Indices of agents requesting ammo
    roles = [-1,-1,-1,-1,-1,-1]

    shootinggoals = [-1, -1, -1, -1, -1, -1]

    EnemyCPS = []
    FriendlySpawn = []
    EnemySpawn = []
    graph = None
    capturingCloseCP = False
    
    def __init__(self, id, team, settings=None, field_rects=None, field_grid=None, nav_mesh=None, blob=None):
        """ Each agent is initialized at the beginning of each game.
            The first agent (id==0) can use this to set up global variables.
            Note that the properties pertaining to the game field might not be
            given for each game.
        """
        #print field_grid
        self.id = id
        self.team = team
        self.mesh = nav_mesh
        self.grid = field_grid
        global g_settings
        g_settings = settings
        self.settings = settings
        self.goal = None
        self.previousRole = None
        self.reachedGoal = False

        self.previousGoal = None
        # Read the binary blob, we're not using it though
        if blob is not None:
            print "Agent %s-%d received binary blob of %s" % (
                ('BLU' if team else 'RED'), id, type(pickle.loads(blob.read())))
            # Reset the file so other agents can read it.
            blob.seek(0) 
        
        # Bind static variables
        self.ammoPacks = self.__class__.ammoPacks
        self.roles = self.__class__.roles
        self.EnemyCPS = self.__class__.EnemyCPS
        self.FriendlySpawn = self.__class__.FriendlySpawn
        self.EnemySpawn = self.__class__.EnemySpawn
	self.capturingCloseCP = self.__class__.capturingCloseCP
        #self.ammoRequestIndices = self.__class__.ammoRequestIndices
        
        # Recommended way to share variables between agents.
        if id == 0:
            self.all_agents = self.__class__.all_agents = []
        self.all_agents.append(self)
        
        # Build map-graph structure:
        if id == 0:
            self.__class__.graph = Graph(nav_mesh)
        self.graph = self.__class__.graph

    def aprint(self, string, ID = 0, team = 0):
        """Agent print function. Prints only for the right agents"""
        if self.id == ID and self.team == team:
            pass
            #print "(" + str(self.id) + ", " + str(self.team) + "): " + str(string)

    """Special purpose observation functions for each agent.
    May be overwritten in subclass.
    Called from observe()"""
    def agent0Observe(self):  # First call in each frame
        # Any "per-frame reset code" goes here
        for pack in self.ammoPacks:
            pack.frameBegin()
        
        self.__class__.ammoRequestIndices = []
	
	capturingCloseCP = False

    def agent1Observe(self):
        pass
    def agent2Observe(self):
        pass
    def agent3Observe(self):
        pass
    def agent4Observe(self):
        pass
    def agent5Observe(self):
        pass #print self.graph.unvisited()

    def validTargetNoFriendlyFire(self, obs, target):
	#print(self.id, obs.step,obs.friends, target)
        for x in obs.friends:
            if(line_intersects_circ(obs.loc,target,x[0:2],5.95)):
		#print(x)
                return False #Can shoot, friendly fire!
        return True #we can shoot!

    def determineSelfRole(self, obs):
        ammopacks = filter(lambda x: x[2] == "Ammo", obs.objects)
	currentFoes = []
	for x in obs.foes:
	    if not(self.targetIsEnemySpawn(obs,x[0:2])):
		currentFoes.append(x)
	
        if currentFoes and obs.ammo > 0:
	    self.roles[self.id] = _Combat #set combat... tactical commander can tell us to shoot :)
	    
        elif obs.ammo > 0: #no foes, but we have ammo
            middleCP = filter(lambda x: x[0] == 328, obs.cps)[0][0:2]
            distToMid = ((middleCP[0]-obs.loc[0])**2 + (middleCP[1]-obs.loc[1])**2)**0.5
            if distToMid < 20 and not(self.EnemyCPS): #is no enemy cps, and close to middle, camp
                self.roles[self.id] = _Camping                
            else:
                self.roles[self.id] = _AttackMove #otherwise, move to enemy control points (or the middle if all are taken)
        elif ammopacks: #no foes, no ammo, but we see ammo, so we grab it
            self.roles[self.id] = _GrabbingAmmo
        else: #no foes, not ammo, we see no ammo, first two CPS captured. So there isnt much to do :(
	    closeCP = filter(lambda x: x[0] < 328, self.EnemyCPS)
	    if(closeCP and not self.capturingCloseCP):
		self.capturingCloseCP = True
		self.roles[self.id] = _CapturingCP
		self.goal = closeCP[0:2]
		#print "Heading over to capture!"
            self.roles[self.id] = _Loitering

    def tacticalCommander(self):
        agentsO = []
        agentsAmmo = []
        for i in range(6):
	    currentFoes = []
	    for x in self.all_agents[i].observation.foes:
		if not(self.targetIsEnemySpawn(self.all_agents[i].observation, x[0:2])):
		    currentFoes.append(x)
            agentsO.append(currentFoes)
            agentsAmmo.append(self.all_agents[i].observation.ammo)
        sortedAgentsO = self.sortOnArray(agentsO, agentsAmmo)
        (assignment, foeslist) = self.jointShooting(sortedAgentsO)
        #print assignment
	#print foeslist
        #mapping = [x[0] for x in sortedAgentsO]
        for i in range(6):
            if( not assignment[i] == -1 ):
                self.roles[i] = _Shooting
		#print foeslist[assignment[i]]
                self.all_agents[i].goal = foeslist[assignment[i]][0:2]



    # Assumption: structure is ordered by ammo descending (done above)
    # Joint shooting uses recursive function to determine
    # an assignment to shoot opponents

    def canShoot(self, o,a):
        if(self.all_agents[o].observation.ammo > 0):
            thisLoc = self.all_agents[o].observation.loc
            thisAngle = self.all_agents[o].observation.angle
            targetLoc = a[0:2]
            dx = targetLoc[0]-thisLoc[0] #remove this after Robrechts code integration
            dy = targetLoc[1]-thisLoc[1]
            turn = angle_fix(math.atan2(dy, dx)-thisAngle)
	    #print ("o:",o,"a:",a,point_dist(targetLoc, thisLoc) < self.settings.max_range,self.validTargetNoFriendlyFire(self.all_agents[o].observation, targetLoc), turn < self.settings.max_turn and turn > -self.settings.max_turn, not line_intersects_grid(thisLoc, targetLoc, self.grid, self.settings.tilesize))
            if (#we can shoot an enemy
                    point_dist(targetLoc, thisLoc) < self.settings.max_range and #distance is ok
                    self.validTargetNoFriendlyFire(self.all_agents[o].observation, targetLoc) and #not friendly fire
                    turn < self.settings.max_turn and turn > -self.settings.max_turn #make sure turn is ok
                    and not line_intersects_grid(thisLoc, targetLoc, self.grid, self.settings.tilesize)): #and no wall
                return True

        return False

    def sortOnArray(self, array, sort):
        struct = [(i,array[i], sort[i]) for i in range(len(sort))]
        return sorted(struct, key=lambda ammo: ammo[2], reverse=True)
    

    def jointShooting(self, structure):
	structure1 = [x[0] for x in structure]
        #print structure1
        structure2 = [x[1] for x in structure]

        # Create list of each foe that is under attack
        foes = list(set([a for observed in structure2 for a in observed]))
        assignment = range(len(structure2))
	
	#print foes
	
        # attack table is a binary 6x6 matrix containing the connection between nodes
        attacktable = [[0 for i in range(len(foes))] for j in range(len(structure))]
	
	#print structure

        # Determine shootable foes for each agent 
        # Current assumption: all foes in the range of agent are shootable
        # Todo: insert Tijmen's attackcode here in stead of (if (a in o))
        #for o in structure2:
        #    for a in foes:
	#	print (structure1[structure2.index(o)], a)
        #        if (self.canShoot(structure1[structure2.index(o)], a)):
        #            attacktable[structure2.index(o)][foes.index(a)] = 1
        #        else:
        #            attacktable[structure2.index(o)][foes.index(a)] = 0
	#        for o in structure2:
	for o in structure1:
	    for a in foes:
		#print (structure1.index(o), a, self.canShoot(structure1.index(o), a))
                if (self.canShoot(structure1.index(o), a)):
                    attacktable[structure1.index(o)][foes.index(a)] = 1
                else:
                    attacktable[structure1.index(o)][foes.index(a)] = 0
	#print attacktable
        assignment = self.assignmentfunction(attacktable,foes)
	#print assignment
        #for i in range(len(assignment)):
        #    if not assignment[i]==-1:
        #        x = foes[assignment[i]][0]
        #        y = foes[assignment[i]][1]
        #        assignment[i] = (x,y)

        return (assignment, foes)

    def assignmentfunction(self, table, foes):
        o = table[0]

    # Base-case:
    # If table has only length 1, then any assignment of a is okay
        if len(table)==1:
            for a in range(len(o)):
                if(o[a]==1 and not foes[a]==0):
                    return [a]
            return [-1]
        else:
            table = table[1:]
            for a in range(len(o)):
                if(o[a]==1 and not foes[a]==0):
                    newfoes = foes[:]
                    newfoes[a] = 0
                    return [a] + self.assignmentfunction(table,newfoes)
            return [-1] + self.assignmentfunction(table,foes)

    def observe(self, observation):
        """ Each agent is passed an observation using this function,
            before being asked for an action. You can store either
            the observation object or its properties to use them
            to determine your action. Note that the observation object
            is modified in place.
        """
        self.previousGoal = self.goal #set the previous goal
                    
        self.observation = observation
        self.selected = observation.selected

        # Mark my new location as visited:
        self.graph.visit(observation.loc)

        # Execute per-ID observation code (these may be overwritten in subclass)
        if(self.id == 0):
            self.agent0Observe()
        elif(self.id == 1):
            self.agent1Observe()
        elif(self.id == 2):
            self.agent2Observe()
        elif(self.id == 3):
            self.agent3Observe()
        elif(self.id == 4):
            self.agent4Observe()
        elif(self.id == 5):
            self.agent5Observe()

        #on the first step, for each agent, determine where the self and opponent spawn is
        if(observation.step == 1):
            self.FriendlySpawn.append(observation.loc)
            self.EnemySpawn.append((656-observation.loc[0],observation.loc[1]))
            #print "EnemySpawn: " + str(self.EnemySpawn)
                
        #agent 0 determines the enemy control points
        if(self.id == 0): 
            del self.EnemyCPS[:]
            for x in range(len(observation.cps)): 
                if observation.cps[x][2] != self.team:
                    self.EnemyCPS.append(observation.cps[x])         
                    
        # Check if agent reached previously set goal.
        if self.goal is not None and point_dist(self.goal, observation.loc) < self.settings.tilesize:
            self.reachedGoal = True
        else:
            self.reachedGoal = False
            
        #-- Assign initial roles to the agent based on own state
        self.previousRole = self.roles[self.id] #store the previous role for continuation
        self.determineSelfRole(self.observation)
        #-- 
       
        #if len(self.ammoPacks) < 6:
        # Process ammo observations
        packObs = filter(lambda x: x[2] == "Ammo", observation.objects)
        self.processAmmoObservations(packObs, observation.loc)

        # Request ammo pack if needed
        if(self.roles[self.id] == _Loitering or self.roles[self.id] == _GrabbingAmmo):
            self.__class__.ammoRequestIndices.append(self.id)
            for pack in self.ammoPacks: # NOTE: at this point, ammoPacks may not contain packs spotted in this frame by later agents..
                #TODO: consider only safe packs
                #path = find_path(observation.loc, (pack.x, pack.y), self.mesh, self.grid, self.settings.tilesize)
                #length = pathLength(observation.loc, path)
                #steps = stepsToTarget(observation.loc, observation.angle, path, length)
                #pack.requests.append([self, path, length, steps, False])
                pack.requestAmmo(self)

        #if self.id == 0 and self.team == 0:
        #    print self.__class__.ammoPacks

        if self.id == 0 and self.team == 0:
            pass
            #print self.__class__.ammoPacks
        
        if(self.id == 5):
            self.tacticalCommander() #The tactical commander reassigns roles and targets!
        #if(self.id == 5 and self.team == 1):  
            #print self.roles[self.id]

    def processAmmoObservations(self, packObs, loc):
        """Takes the ammo observations of an agent as well as the agents location,
           checks if it contains ammo observations not registered before,
           and adds those to the shared knowledge of ammo packs.
           Also signals the presence or absense of all known packs in range."""
        # Function can surely be made much more efficient.

        # Get a list of ammopacks that we should be able to see
        observables = filter(lambda pack: inRangeManhattan((pack.x,pack.y),loc,g_settings.max_see),
                             self.__class__.ammoPacks)
        
        # Signal observations of known packs, or add pack if unknown
        for ob in packObs:
            seenBefore = False
            for pack in self.__class__.ammoPacks: #observables: #for pack in type(self).ammoPacks:
                if pack.x == ob[0] and pack.y == ob[1]:
                    pack.observedPresent()
                    seenBefore = True
                    break
            if not seenBefore:
                self.__class__.ammoPacks.append(AmmoPack(ob[0],ob[1],self.settings.ammo_rate))
                self.__class__.ammoPacks.append(AmmoPack(656 - ob[0],ob[1],self.settings.ammo_rate))
                assert(len(self.__class__.ammoPacks) <= 6)
                #self.aprint("New ammo pack discovered ", self.id)
                # Add requests to new packs for all previous agents requiring ammo 
                for agentId in self.__class__.ammoRequestIndices:
                    self.aprint("Adding request: " + str(len(self.ammoPacks) - 1) + ", " + str(agentId), self.id)
                    self.ammoPacks[len(self.ammoPacks) - 1].requestAmmo(self.all_agents[agentId])
                    self.ammoPacks[len(self.ammoPacks) - 2].requestAmmo(self.all_agents[agentId])
                

        # Signal absence of pack
        for pack in observables:
            wasObservedPresent = False
            for ob in packObs:
                if pack.x == ob[0] and pack.y == ob[1]:
                    wasObservedPresent = True
            if not wasObservedPresent:
                pack.observedAbsent()
                       
    
    def distributeAmmo(self):
        
        # Get a list of pointers to all agents requiring ammo
        self.aprint('requesters: ' + str(self.__class__.ammoRequestIndices))
        agents = []
        for i in self.__class__.ammoRequestIndices:
            agents.append(self.all_agents[i])
        if len(agents) == 0:
            return ([],[])

        # Get a list of pointers to all ammo packs, padded with Nones if needed
        packs = list(self.ammoPacks)
        if len(packs) == 0:
            return ([],[])
        while len(agents) > len(packs): # If there are more agents requiring ammo than packs that are available (known), some agents get None ammo
            packs.append(None)

        minCost = 99999999
        minAssignment = []
        
        for assignment in permutations(packs, len(agents)): # Contains duplicates if there are more agents than packs.. Only happens early in the game and only affects speed
            
            # Calculate the cost of this assignment
            cost = 0
            for i in range(len(assignment)):
                if assignment[i] != None:
                    request = assignment[i].requests[agents[i].id]
                    #self.aprint('request: ' + str(assignment[i].requests))
                    cost += max(request[3], assignment[i].availableIn)
                else:
                    cost += 0 # TODO: variable cost for not assigning to a particular agent
            if cost < minCost:
                minCost = cost
                minAssignment = assignment
        
        #print "MINASSIGNMENT: " + str(minAssignment)
        return (agents, minAssignment)


    """Special purpose action functions for each agent.
    May be overwritten in subclass.
    Called from action()"""
    def agent0Action(self):
        for pack in self.ammoPacks:
            pack.frameEnd()
        
        if self.team == 0:
            self.aprint("Ammo packs: ",self.id)
            for pack in self.ammoPacks:
                self.aprint(pack,self.id)

        (agents, packs) = self.distributeAmmo()
        if not(len(agents) == 0):
            for i in range(len(agents)):
                if not(packs[i] == None):
                    stepstillspawn = packs[i].availableIn
                    stepstillarrival = packs[i].requests[agents[i].id][4]
                    if stepstillspawn - 1 <= stepstillarrival:
                        agents[i].goal = (packs[i].x,packs[i].y)
                        self.roles[agents[i].id] = _LookingForAmmo
                    else:
                        self.roles[agents[i].id] = _Loitering
                else:
                    self.roles[agents[i].id] = _Loitering
        
    def agent1Action(self):
        pass
    def agent2Action(self):
        pass
    def agent3Action(self):
        pass
    def agent4Action(self):
        pass
    def agent5Action(self):
        pass
    def targetIsEnemySpawn(self,obs,target):
        #spawn = filter(lambda x: x[0] == target[0] and x[1] == target[1], self.EnemySpawn)
        for x in self.EnemySpawn:
            if line_intersects_circ(obs.loc, target, x, 9.0):
                return True
        return False
    
    def setGoalLoitering(self, obs):
        self.roles[self.id] = _Loitering #in case other functions fail, this is called and our goal becomes loitering
        if self.previousRole == _Loitering and not self.reachedGoal :#if we were already loitering and did not get to the goal yet, but we have a goal
	    if(len(self.ammoPacks) < 6 and obs.step > 30): #we have not found all ammopacks yet, go explore the space!
		unvisitedVertices = self.graph.unvisited() 
		if(unvisitedVertices):
		    numUnvisitedVertices = len(unvisitedVertices)
		    self.goal = unvisitedVertices[random.randint(0,numUnvisitedVertices-1)]
		    return self.goal
            CurrentCPTarget = filter(lambda x: x[0] == self.goal[0] and x[1] == self.goal[1], obs.cps)#
            if CurrentCPTarget:
                if(CurrentCPTarget[0][2] == self.team): #if the goal we have is not an enemy CP anymore, move to another random one
                    pass
                else:
                    return self.goal #keep the goal if we were previously loitering
            pass
        if(self.EnemyCPS):#otherwise, we set an enemy control point as a goal to meattank capture!
            if obs.step > 20: #do it random in the first 20 steps
                self.goal = self.EnemyCPS[random.randint(0,len(self.EnemyCPS)-1)][0:2]
            else: #then keep on capturing the closest CP! (not pathwise... because that is expensive :/)
                minimumDist = ((obs.loc[0] - self.EnemyCPS[0][0])**2 + (obs.loc[1] - self.EnemyCPS[0][1])**2)**0.5
                closestCP = self.EnemyCPS[0][0:2]
                for x in self.EnemyCPS:
                    dist = ((obs.loc[0] - x[0])**2 + (obs.loc[1] - x[1])**2)**0.5
                    if dist < minimumDist:
                        minimumDist = dist
                        closestCP = x[0:2]
                self.goal = closestCP
        else: #if all control points are captured, go to the middle one + offset
            self.goal = filter(lambda x: x[0] == 328, obs.cps)[0][0:2]
            targetx = self.goal[0] + random.randint(-20,20)
            targety = self.goal[1] + random.randint(-20,20)
            if not line_intersects_grid(obs.loc, (targetx, targety), self.grid, self.settings.tilesize):
                self.goal = (targetx, targety)
        return self.goal
    def setGoalGrabbingAmmo(self, obs):
        ammopacks = filter(lambda x: x[2] == "Ammo", obs.objects)
        if ammopacks: #check if we actually have ammopacks close by...
            self.goal = ammopacks[0][0:2] #go grab the closest ammo pack
        else: 
            return self.setGoalLoitering(obs) #no ammopacks, do something else
        return self.goal
    def setGoalLookingForAmmo(self, obs):#The goal is already set to the target pack!
        return self.goal
    def setGoalAttackMove(self, obs):
        if self.previousRole == _AttackMove and not self.reachedGoal:#if we were already attackmoving and did not get to the goal yet, but we have a goal
            CurrentCPTarget = filter(lambda x: x[0] == self.goal[0] and x[1] == self.goal[1], obs.cps) #
            if CurrentCPTarget:
                if(CurrentCPTarget[0][2] == self.team): #if the goal we have is not an enemy CP anymore, move to another random one
                    pass
                else:
                    return self.goal #keep the target if we were attack moving there first :)
            pass
        
        if(self.EnemyCPS):#otherwise, we set an enemy control point as a goal to capture!
            if obs.step > 20: #do it random in the first 20 steps
                self.goal = self.EnemyCPS[random.randint(0,len(self.EnemyCPS)-1)][0:2]
            else: #then keep on capturing the closest CP! (not pathwise... because that is expensive :/)
                minimumDist = ((obs.loc[0] - self.EnemyCPS[0][0])**2 + (obs.loc[1] - self.EnemyCPS[0][1])**2)**0.5
                closestCP = self.EnemyCPS[0][0:2]
                for x in self.EnemyCPS:
                    dist = ((obs.loc[0] - x[0])**2 + (obs.loc[1] - x[1])**2)**0.5
                    if dist < minimumDist:
                        minimumDist = dist
                        closestCP = x[0:2]
                self.goal = closestCP
        else: #if all control points are captured, go to the middle one + offset
            self.goal = filter(lambda x: x[0] == 328, obs.cps)[0][0:2]
            targetx = self.goal[0] + random.randint(-20,20)
            targety = self.goal[1] + random.randint(-20,20)
            if not line_intersects_grid(obs.loc, (targetx, targety), self.grid, self.settings.tilesize):
                self.goal = (targetx, targety)
        return self.goal
    def setGoalCombat(self, obs):
        if obs.foes: #set the first enemy as goal (still naive)
            return obs.foes[0][0:2]        
        else: 
            return self.setGoalLoitering(obs) #if no foes, loiter
        return self.goal
    def setGoalShooting(self, obs):
        #assuming that the self.goal is already set to the target that is to be shot!
        return self.goal
    def setGoalCamping(self, obs):#camp this position! Turn towards enemy spawn
        return (self.EnemySpawn[0])
    def naiveMoveTo(self,obs):
        path = find_path(obs.loc, self.goal, self.mesh, self.grid, self.settings.tilesize)
        if path:
            dx = path[0][0]-obs.loc[0]
            dy = path[0][1]-obs.loc[1]
            turn = angle_fix(math.atan2(dy, dx)-obs.angle)
            if(turn < math.pi/2 and turn > -math.pi/2): #if movement target is in front of the agent
                speed = (dx**2 + dy**2)**0.5
            else: #target in the back, turn around first
                speed = 1
        else:
            turn = 0
            speed = 0
        return (turn,speed)
    def processLoitering(self, obs):
        (turn, speed) = self.naiveMoveTo(obs)
        shoot = False
        return (turn,speed,shoot)
    def processGrabbingAmmo(self, obs):
        (turn, speed) = self.naiveMoveTo(obs)
        shoot = False
        return (turn,speed,shoot)
    def processAttackMove(self, obs):
        (turn, speed) = self.naiveMoveTo(obs)
        shoot = False
        return (turn,speed,shoot)
    def processCaptureCP(self, obs):
        (turn, speed) = self.naiveMoveTo(obs)
        shoot = False
        return (turn,speed,shoot)
    def processCombat(self, obs):
        (turn, speed) = self.naiveMoveTo(obs)
        shoot = False
        #rectify forward movement if the opponent is heading toward you
        if obs.foes:
            CurrentEnemyTarget = filter(lambda x: x[0] == self.goal[0] and x[1] == self.goal[1], obs.foes)
            
            if CurrentEnemyTarget:
                EnemyAngle = CurrentEnemyTarget[0][2]
                AngleDif = abs(angle_fix(abs(EnemyAngle - obs.angle)))
                if AngleDif > 5*math.pi/6 and not line_intersects_grid(obs.loc, self.goal, self.grid, self.settings.tilesize):
                    if speed > 1:
                        speed = 5
                        #print (self.id, "Restricting Speed ")
        return (turn,speed,shoot)
    def processCamping(self, obs): #turn towards the enemy spawn
        (turn, speed) = self.naiveMoveTo(obs)
        shoot = False
        return (turn,speed,shoot)
    def processShooting(self, obs):
        #shoot the target, assuming that self.goal contains the target and it is tagged as shootable
        dx = self.goal[0]-obs.loc[0]
        dy = self.goal[1]-obs.loc[1]
        turn = angle_fix(math.atan2(dy, dx)-obs.angle) #turn towards the target
        
        shoot = True
        speed = 0
        
        #check if the target is in a spawn location.. do not shoot!
        if self.targetIsEnemySpawn(obs, self.goal):
            shoot = False
            
        return (turn, speed, shoot)
    def processLookingForAmmo (self,obs):
        (turn, speed) = self.naiveMoveTo(obs)
        shoot = False
        return (turn,speed,shoot)
    def action(self):
        """ This function is called every step and should
            return a tuple in the form: (turn, speed, shoot)
        """
        
        #print(self.id,self.roles[self.id])
        
        if(self.id == 0):
            self.agent0Action()
        elif(self.id == 1):
            self.agent1Action()
        elif(self.id == 2):
            self.agent2Action()
        elif(self.id == 3):
            self.agent3Action()
        elif(self.id == 4):
            self.agent4Action()
        elif(self.id == 5):
            self.agent5Action()

        obs = self.observation
        
        #set the goals for these actions
        if(self.roles[self.id] == _Loitering ):
            self.goal = self.setGoalLoitering(obs);
        elif (self.roles[self.id] == _GrabbingAmmo ):
            self.goal = self.setGoalGrabbingAmmo(obs);
        elif (self.roles[self.id] == _LookingForAmmo ):
            self.goal = self.setGoalLookingForAmmo(obs);
        elif (self.roles[self.id] == _AttackMove ):
            self.goal = self.setGoalAttackMove(obs);
        elif (self.roles[self.id] == _Combat ):
            self.goal = self.setGoalCombat(obs);
        elif (self.roles[self.id] == _Shooting ):
            self.goal = self.setGoalShooting(obs);
        elif (self.roles[self.id] == _Camping):
            self.goal = self.setGoalCamping(obs);

        
        #process the actions
        if(self.roles[self.id] == _Loitering ):
            (turn,speed,shoot) = self.processLoitering(obs);
        elif (self.roles[self.id] == _GrabbingAmmo ):
            (turn,speed,shoot) = self.processGrabbingAmmo(obs);
        elif (self.roles[self.id] == _LookingForAmmo ):
            (turn,speed,shoot) = self.processLookingForAmmo (obs);
        elif (self.roles[self.id] == _AttackMove ):
            (turn,speed,shoot) = self.processAttackMove(obs);
        elif (self.roles[self.id] == _Combat ):
            (turn,speed,shoot) = self.processCombat(obs);
        elif (self.roles[self.id] == _Shooting ):
            (turn,speed,shoot) = self.processShooting(obs);
        elif (self.roles[self.id] == _Camping ):
            (turn,speed,shoot) = self.processCamping(obs);
	elif (self.roles[self.id] == _CapturingCP):
            self.goal = self.processCaptureCP(obs);
        else:
            assert(False)
        """
        # Walk to ammo
        ammopacks = filter(lambda x: x[2] == "Ammo", obs.objects)
        if ammopacks:
            self.goal = ammopacks[0][0:2]
            
        # Drive to where the user clicked
        if self.selected and self.observation.clicked:
            self.goal = self.observation.clicked
        
        # Walk to random CP
        if self.goal is None:
            self.goal = obs.cps[random.randint(0,len(obs.cps)-1)][0:2]
        
        # Shoot enemies
        shoot = False
        if (obs.ammo > 0 and 
            obs.foes and 
            point_dist(obs.foes[0][0:2], obs.loc) < self.settings.max_range
            and not line_intersects_grid(obs.loc, obs.foes[0][0:2], self.grid, self.settings.tilesize)):
            self.goal = obs.foes[0][0:2]
            shoot = True

        # Compute path, angle and drive
        t1 = time.time()
        path = find_path(obs.loc, self.goal, self.mesh, self.grid, self.settings.tilesize)
        t2 = time.time()
        #print 'Path planning took %0.3f ms' % ((t2-t1)*1000.0)

        if path:
            dx = path[0][0]-obs.loc[0]
            dy = path[0][1]-obs.loc[1]
            turn = angle_fix(math.atan2(dy, dx)-obs.angle)
            if turn > self.settings.max_turn or turn < -self.settings.max_turn:
                shoot = False
            speed = (dx**2 + dy**2)**0.5
        else:
            turn = 0
            speed = 0
        """
        #if(self.id == 5 and self.team == 0):  
         #   print self.goal, (turn,speed,shoot)
        return (turn,speed,shoot)
        
    def debug(self, surface):
        """ Allows the agents to draw on the game UI,
            Refer to the pygame reference to see how you can
            draw on a pygame.surface. The given surface is
            not cleared automatically. Additionally, this
            function will only be called when the renderer is
            active, and it will only be called for the active team.
        """
        import pygame
        # First agent clears the screen
        if self.id == 0:
            surface.fill((0,0,0,0))
        # Selected agents draw their info
        if self.selected:
            if self.goal is not None:
                pygame.draw.line(surface,(0,0,0),self.observation.loc, self.goal)
	if self.roles[self.id] == _Shooting:
	    pygame.draw.circle(surface, (255,0,0), self.observation.loc, 6,1)
	if self.roles[self.id] == _Combat:
	    pygame.draw.circle(surface, (0,255,255), self.observation.loc, 6,1)
	    for x in self.observation.foes:
		if not(self.validTargetNoFriendlyFire(self.observation, x[0:2])):
		    #pygame.draw.line(surface,(255,0,0),self.observation.loc, x[0:2])
		    pass
	    for x in self.observation.foes:
		if not(point_dist(x[0:2], self.observation.loc) < self.settings.max_range):
		    #pygame.draw.line(surface,(0,255,0),self.observation.loc, x[0:2])
		    pass
	    for x in self.observation.foes:
		if not(getTurn(self.observation.loc, x[0:2], self.observation.angle) < self.settings.max_turn and getTurn(self.observation.loc, x[0:2], self.observation.angle) > - self.settings.max_turn ):
		    #pygame.draw.line(surface,(0,0,255),self.observation.loc, x[0:2])
		    pass
		    
	    for x in self.observation.foes:
		if line_intersects_grid(self.observation.loc, x[0:2], self.grid, self.settings.tilesize):
		    #pygame.draw.line(surface,(255,255,255),self.observation.loc, x[0:2])
		    pass
	    for x in self.observation.foes:
		if self.canShoot(self.id,x):
		    pygame.draw.line(surface,(255,0,0),self.observation.loc, x[0:2])
		    pass
		
	
        
    def finalize(self, interrupted=False):
        """ This function is called after the game ends, 
            either due to time/score limits, or due to an
            interrupt (CTRL+C) by the user. Use it to
            store any learned variables and write logs/reports.
        """
        pass
        

# Dummy class. Edit the class it derives from to choose your class
class Agent(AgentBase):
    NAME = "Tijmens_Regret"
    pass